/*
题目: 水位上升的泳池中游泳
在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

https://leetcode.cn/problems/swim-in-rising-water/
 */
public class SwimInWater {
    Set<String> visited ;
    int[] dir = new int[] {0, -1, 0, 1, 0};
    int n;
    public int swimInWater(int[][] grid) {
        n = grid.length;
        Queue<int[]> queue = new LinkedList<> ();
        visited = new HashSet<> ();

        int time = 0;  // 时间 同时也是水位
        queue.offer(new int[] {0, 0});
        visited.add(new String("0") + ',' + new String("0"));

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                int[] cur = queue.poll();
                // 当前格子有水 并且可以 直接游到终点
                if (grid[cur[0]][cur[1]] <= time) {
                    if (bfs(queue, grid, cur, time))    return time;
                } else {
                    queue.offer(cur);  // 这个 格子暂时没有水 放回去待处理
                }
            }
            time ++;
        }

        return time;
    }

    private boolean bfs(Queue<int[]> queue, int[][] grid, int[] cur, int time) {
        // 到达终点
        if (cur[0] == n - 1 && cur[1] == n - 1) {
            return true;
        }

        for (int i = 0; i < 4; i ++) {
            int nextX = cur[0] + dir[i];
            int nextY = cur[1] + dir[i + 1];
            String nextStr = String.valueOf(nextX) + "," + String.valueOf(nextY);
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || visited.contains(nextStr)) continue ;

            visited.add(nextStr);  // 标记为访问过
            // 下一格可以直接游过去  并且可以 直接到达终点
            if (grid[nextX][nextY] <= time) {
                if (bfs(queue, grid, new int[] {nextX, nextY}, time))   return true;
            } else { // 游不过去就等待
                queue.offer(new int[] {nextX, nextY});
            }
        }
        return false;
    }
}
